/**
 * @version: V1.0
 * @Title: Test05_IsCBT.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-25 22:57
 * @Copyright: 2022-01-25
 */

package com.peng.tree.test_code;

import com.peng.tree.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author wangshipeng
 * @ClassName: Test05_IsCBT
 * @Description:
 *
 * 是否是完全二叉树 需要符合2个特征：
 * 1、一个节点如果有右孩子节点，必须要有左孩子节点
 * 2、一个节点如果左右孩子不全，那么它必须是叶子节点
 *
 * @date 2022-01-25 22:57
 */
public class Test05_IsCompleteBinaryTree {

    public static boolean isCBT(Node head) {
        if (head == null) {
            return true;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        boolean isLeaf = false;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            //只有右节点
            if (cur.left == null && cur.right != null) {
                return false;
            }
            //出现过左右子孩子不全的情况，但后续的节点却不是一个叶子节点
            if (isLeaf && cur.left != null) {
                return false;
            }


            //出现左右子孩子不全的情况，设置标记，如果是一颗完全二叉树，那么后续的节点理应都将是没有孩子节点的叶子节点
            if (cur.left == null || cur.right == null) {
                isLeaf = true;
            }

            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }

        return true;

    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;

                /*
                   1
             2              3
           4    5         6     7
         8   9

         */

        System.out.println(isCBT(node));
    }


}
